package com.zklh.leetcode.dynamic;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 三角形最小路径和
 *
 * @author tongnan
 * @date 2025/9/29
 */
public class Solution120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        triangle = triangle.stream().map(ArrayList::new).collect(Collectors.toCollection(ArrayList::new));
        List<List<Integer>> minPath = new ArrayList<>(triangle);
        minPath.add(new ArrayList<>(Collections.nCopies(triangle.get(triangle.size()-1).size(), 0)));

        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                minPath.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i+1).get(j), triangle.get(i+1).get(j+1)));
            }
        }
        return triangle.get(0).get(0);
    }
}
